/**
 * @desc 75. Sort Colors
 * 
 *  Input: [2,0,2,1,1,0]
    Output: [0,0,1,1,2,2]

    最容易想到的是计数排序
    但要求：
        原地排序in place 即不使用额外空间
    选择一个额外空间为1的排序不就行了？
        冒泡？归并x(递归有栈) 快速x 
        选择 插入
 */
/*
var sortColors = function(arr) {
    if(arr==null||arr.length<2){
        return ;
    }
    for(let len = arr.length;len>0;len--){
        for(let j=0;j<len;j++){
            if(arr[j]>arr[j+1]){
                swap(arr,j,j+1)
            }
        }
    }
};

function swap(arr,i,j){
    [arr[i],arr[j]]  = [arr[j],arr[i]];
}
*/
/*
var sortColors = function(arr) {
    if(arr==null||arr.length<2){
        return ;
    }
    // 插入排序
    for(let i=1;i<arr.length;i++){
        for(let j = i-1;j>=0&&arr[j]>arr[j+1];j--){
            swap(arr,j,j+1)
        }
    }
};

function swap(arr,i,j){
    [arr[i],arr[j]]  = [arr[j],arr[i]];
}

*/

// 选择排序
var sortColors = function(arr) {
    if(arr==null||arr.length<2){
        return ;
    }

    for(let i=0;i<arr.length;i++){
        let minIndex = i;
        for(let j=i+1;j<arr.length;j++){
            minIndex = arr[j]<arr[minIndex]?j:minIndex;
        }
        swap(arr,minIndex,i);
    }
}

function swap(arr,i,j){
    [arr[i],arr[j]]  = [arr[j],arr[i]];
}